Semiconductor memory devices, including flash memory, typically utilize memory cells to store data as an electrical value, such as an electrical charge or voltage. A flash memory cell, for example, includes a single transistor with a floating gate that is used to store a charge representative of a data value. Flash memory is a non-volatile data storage device that can be electrically erased and reprogrammed. More generally, non-volatile memory (e.g., flash memory, as well as other types of non-volatile memory implemented using any of a variety of technologies) retains stored information even when not powered, as opposed to volatile memory, which requires power to maintain the stored information.
As flash memory storage systems grow in size, the efficiency with which data stored by flash memory can be accessed becomes more important. Tiered data structures can be used to improve the speed and efficiency of data access. Some tiered data structures enable data searches, data insertions, data deletions, and sequential data access to be performed in logarithmic time. Often, a tiered data structure is used for mapping physical locations of stored data in flash memory to logical addresses. However, when the average size of data writes is small, memory consumed by a tiered data structure may increase dramatically. Improvements to tiered data structure components can reduce the amount of memory consumed by the tiered data structure.